Data processing systems require efficient data storage means to ensure successful operation of the system. Data not only needs to be available upon request, but also must be accurate and represent the latest version upon retrieval. Methods of storing replicas of data on different storage entities are usually utilized to provide back-up copies of data during unexpected storage entity failures. However, since the storage entities may fail while updating data replicas, there is a need for algorithms providing retrieval of the most recent successful update, i.e. algorithms providing a consensus on the value stored in the system, independently of the failed storage entities.
There are several distributed consensus algorithms currently utilized in the industry. One of the algorithms is the Butler Lampson extension of a well-known Paxos algorithm. The Butler Lampson consensus algorithm requires data to be replicated on all the data storage entities in a system. Most of the time, there is no need for such a large number of data replicas. Moreover, replication of data on all the data storage entities present in the system becomes resource and time consuming operation and impedes scalability of the system if a number of storage entities is large. In addition, a failure of each storage entity in the system reduces data availability, because the number of data storage entities storing a data replica decreases with each failure. What is needed, therefore, is a solution that overcomes these and other shortcomings of the prior art.